package org.hot100.h105;

/**
 * @Author: wjy
 * @Date: 2021/12/30 9:14
 */
public class Solution {

    public static void main(String[] args) {

        /*int[] preorder = {3, 9, 20, 15, 7};
        int[] inorder = {9, 3, 15, 20, 7};*/
        int[] preorder = {1, 2, 3};
        int[] inorder = {3, 2, 1};

        Solution solution = new Solution();
        TreeNode treeNode = solution.buildTree(preorder, inorder);
        System.out.println(treeNode.val);

    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        // 分治！！！！！！！！！！！！！！！
        return build4(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }

    public TreeNode build(int[] preorder, int pstart, int pend, int[] inorder, int istart, int iend) {
        if (pstart == pend || istart == iend) {
            return null;
        }

        // 首先找到中序遍历根节点
        int irootIndex = 0;
        for (int i = istart; i < iend; i++) {
            if (preorder[pstart] == inorder[i]) {
                irootIndex = i;
                break;
            }
        }

        int length = irootIndex - istart;

        // 将大问题拆成一个个小问题！！！
        // 左节点
        TreeNode left = build(preorder, pstart + 1, pstart + length + 1, inorder, istart, irootIndex);

        // 右节点
        TreeNode right = build(preorder, pstart + length + 1, pend, inorder, irootIndex + 1, iend);

        return new TreeNode(inorder[irootIndex], left, right);
    }

    public TreeNode build2(int[] preorder, int pstart, int pend, int[] iorder, int istart, int iend) {
        if (pstart == pend || istart == iend) {
            return null;
        }

        int imid = 0;
        for (int i = 0; i < iend; i++) {
            if (iorder[i] == preorder[pstart]) {
                imid = i;
                break;
            }
        }

        int ilength = imid - istart;

        TreeNode left = this.build2(preorder, pstart + 1, pstart + ilength + 1, iorder, istart, imid);
        TreeNode right = this.build2(preorder, pstart + ilength + 1, pend, iorder, imid + 1, iend);
        return new TreeNode(iorder[imid], left, right);
    }

    public TreeNode build3(int[] preorder, int pstart, int pend, int[] iorder, int istart, int iend) {
        if (pstart == pend || istart == iend) {
            return null;
        }

        int ilength = 0;
        for (int i = istart; i < iend; i++) {
            if (iorder[i] == preorder[pstart]) {
                ilength = i - istart;
            }
        }

        TreeNode left = build3(preorder, pstart + 1, pstart + ilength + 1, iorder, istart, istart + ilength);
        TreeNode right = build3(preorder, pstart + ilength + 1, pend, iorder, istart + ilength + 1, iend);
        return new TreeNode(preorder[pstart], left, right);
    }

    // 3, 9, 20, 15, 7
    // 9, 3, 15, 20, 7
    public TreeNode build4(int[] preorder, int pstart, int pend, int[] iorder, int istart, int iend) {
        if (pstart == pend || istart == iend) {
            return null;
        }

        int ilength = 0;
        for (int i = istart; i < iorder.length; i++) {
            if (preorder[pstart] == iorder[i]) {
                ilength = i - istart;
                break;
            }
        }

        TreeNode left = build4(preorder, pstart + 1, pstart + ilength + 1, iorder, istart, ilength);
        TreeNode right = build4(preorder, pstart + ilength + 1, pend, iorder, istart + ilength + 1, iend);
        return new TreeNode(preorder[pstart], left, right);
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}